﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace TP_EDA_5847
{
    class KDTree
    {
        public No root;

        /// <summary>
        /// Constructor.
        /// </summary>
        public KDTree()
        {
            this.root = null;
        }

        /// <summary>
        /// Find the best point to start the tree
        /// </summary>
        /// <param name="listNos">List of nodes</param>
        /// <returns>the best point cosest to the median</returns> 
        public No balanceNos(List<No> listNos)
        {
            var sortedNosList = listNos.OrderBy(p => p.value[0]);
            int count = 0;
            foreach (No x in listNos)
            {
                count += x.value[0];
            }
            double median = count / listNos.Count;

            No lastOne = null;
            foreach (No x in sortedNosList)
            {
                if (x.value[0] > median)
                {
                    return lastOne;
                }
                lastOne = x;
            } 
            return null;
        }

        /// <summary>
        /// Sort the list of nodes by X searching the closest point to the median
        /// </summary>
        /// <param name="listNos">List of nodes</param>
        /// <returns>List of sorted nodes</returns> 
        public List<No> sortListNos(List<No> listNos)
        {
            List<No> NewListNos = new List<No>();
            No rootPoint = balanceNos(listNos);
            NewListNos.Add(rootPoint);
            List<No> lower = new List<No>();
            List<No> hight = new List<No>();
            foreach (No no in listNos)
            {
                if (no != rootPoint)
                {
                    if (no.value[0] >= rootPoint.value[0])
                    {
                        hight.Add(no);
                    }
                    else
                    {
                        lower.Add(no);
                    }
                }
            }
            var sortedHight = hight.OrderBy(p => p.value[0]);
            var sortedlower = lower.OrderByDescending(p => p.value[0]);
            foreach (No no in sortedlower)
            {
                NewListNos.Add(no);
            }
            foreach (No no in sortedHight)
            {
                NewListNos.Add(no);
            }

            return NewListNos;
        }

        /// <summary>
        /// Insert the node
        /// </summary>
        /// <param name="node">The node to insert</param>
        public void insert(No node){
            No y = null;
            No x = this.root;
            int i = node.value.Count - 1;
            while (x != null)
            {
                i = tradeToXYZ(i, node.value.Count);
                y = x;
                if (node.value[i] < x.value[i])
                {
                    x = x.left;
                }
                else
                {
                    x = x.right;
                }
            }
            node.parent = y;
            if (y == null)
            {
                this.root = node;
            }
            else if (node.value[i] < y.value[i])
            {
                y.left = node;
            }
            else
            {
                y.right = node;
            }
        }

        /// <summary>
        /// Trade to X, Y or Z, depends the line
        /// </summary>
        /// <param name="i">the line</param>
        /// <param name="listSize">size of the node value</param>
        /// <returns> 1 = X || 2 = Y || 3 = Z</returns> 
        public int tradeToXYZ(int i, int listSize)
        {
            if(listSize == 2){
                if (i == 1)
                {
                    return 0;
                }
                else
                {
                    return 1;
                }
            }
            else // if == 3
            {
                if (i == 2){
                    return 0;
                }
                else if(i == 1){
                    return 2;
                }
                else{
                    return 1;
                }
            }
        }

        /// <summary>
        /// Search on tree.
        /// </summary>
        /// <param name="node">the node to search</param>
        /// <returns> Fouded = Node fouded || Not Founded = Null</returns> 
        public No search(No node)
        {
            No y = null;
            No x = this.root;
            int i = node.value.Count - 1;
            while (node.value[0] != x.value[0] || node.value[1] != x.value[1])
            {
                i = tradeToXYZ(i, node.value.Count);
                y = x;
                if (node.value[i] < x.value[i])
                {
                    x = x.left;
                }
                else
                {
                    x = x.right;
                }
                if (x == null)
                {
                    return new No(null);
                }
            }
            return x;
        }

        /// <summary>
        /// Remove the node from the Tree
        /// </summary>
        /// <param name="listNodes">the list of Nodes</param>
        /// <param name="z">the node to remove</param>
        /// <returns>the list of nodes with the point alredy removed</returns>
        public List<No> remove(List<No> listNodes, No z)
        {
            listNodes.Remove(z);
            listNodes = sortListNos(listNodes);
            this.root = null;
            foreach (No no in listNodes)
            {
                no.clean();
                insert(no);
            }
            return listNodes;
        }

        /// <summary>
        /// Calculate the distance bitwen 2 points
        /// </summary>
        /// <param name="point">the first point</param>
        /// <param name="point2">the secound point</param>
        /// <returns> the distance</returns>
        public double calculateDistance(List<int> point, List<int> point2)
        {
            double distance = 0.0;
            for (int x = 0; x < point.Count; x++)
            {
                distance += Math.Pow(Math.Abs(point[x] - point2[x]), 2); 
            }
            distance = Math.Sqrt(distance);
            return distance;
        }

        /// <summary>
        /// Seach the nearest neighbour of the point
        /// </summary>
        /// <param name="point">the point</param>
        /// <returns> The best point || the nearest neighbour</returns>
        public No NearestNeighBour(List<int> point)
        {
            No currentBest = this.root;
            double currentBestDistance = 0.0;
            if (point[0] >= this.root.value[0])
            {
                currentBest = TryFindBestNeighBour(point, this.root.right);
                No leftCurrentBest = TryFindBestNeighBour(point, this.root.left);
                if (calculateDistance(point, currentBest.value) > calculateDistance(point, leftCurrentBest.value))
                {
                    currentBest = leftCurrentBest;
                }
            }
            else
            {
                currentBest = TryFindBestNeighBour(point, this.root.left);
                No rightCurrentBest = TryFindBestNeighBour(point, this.root.right);
                if (calculateDistance(point, currentBest.value) > calculateDistance(point, rightCurrentBest.value))
                {
                    currentBest = rightCurrentBest;
                }
            }

            if (calculateDistance(point, this.root.value) < currentBestDistance)
            {
                return this.root;
            }
            else
            {
                return currentBest;
            }
        }

        /// <summary>
        /// Try to find the closest point betwen the current point and the next point
        /// </summary>
        /// <param name="point">the point</param>
        /// <param name="currentPoint">the current point</param>
        /// <returns> The best point || the nearest neighbour</returns>
        public No TryFindBestNeighBour(List<int> point, No currentPoint)
        {
            No currentBest = currentPoint;
            double currentBestDistance;

            while (true)
            {
                double? rightDistance = null;
                double? leftDistance = null;
                currentBestDistance = calculateDistance(point, currentBest.value);
                if (currentBest.right != null)
                {
                    rightDistance = calculateDistance(point, currentBest.right.value);
                }
                if(currentBest.left != null){
                    leftDistance = calculateDistance(point, currentBest.left.value);
                }
                if (rightDistance != null && rightDistance < currentBestDistance)
                {
                    currentBest = currentBest.right;
                }else if(leftDistance != null && leftDistance < currentBestDistance){
                    currentBest = currentBest.left;
                }else{
                    return currentBest;
                }
            }
        }
    }
}
